package leetcode_core.leetcode_1;

public class EquationsPossible {

    public boolean equationsPossible(String[] equations) {
        //建立26个字母连通关系
        UnionFind unionFind  = new UnionFind(26);
        for (String equation : equations) {
            if(equation.charAt(1) == '='){
                char x = equation.charAt(0);
                char y = equation.charAt(3);
                unionFind.union(x-'a',y-'a');
            }
        }
        //检查不等关系
        for (String equation : equations) {
            if(equation.charAt(1) == '!'){
                char x = equation.charAt(0);
                char y = equation.charAt(3);
                if(unionFind.isConnected(x-'a',y-'a')){
                    return false;
                }
            }
        }
        return true;
    }

    class UnionFind {
        //记录连通分量
        private int count;
        //数组定义:节点x的父亲节点是parent[x]
        private int[] parent;
        //新增一个数组记录树的重量
        private int[] size;

        public UnionFind(int n) {
            //一开始各自不连通,那么就各自指向自己
            this.count = n;
            parent = new int[n];
            for (int i = 0; i < n; i++) {
                parent[i] = i;
                size[i] = 1;//树的尺寸一开始都是1
            }
        }

        //将p节点和q节点进行链接
        public void union(int p, int q) {
            int rootP = find(p);
            int rootQ = find(q);
            if (rootP == rootQ) {
                return;
            }
            //小树接到大树下面,比较平衡
            if (size[rootP] > size[rootQ]) {
                parent[rootQ] = rootP;
                size[rootP] += size[rootQ];
            } else {
                parent[rootP] += rootQ;
                size[rootQ] += rootP;
            }
            this.count--;
        }

        //判断p和q是否连同
        public boolean isConnected(int p, int q) {
            int rootP = find(p);
            int rootQ = find(q);
            return rootP == rootQ;
        }

        //返回图中有几个连通分量
        public int count() {
            return count;
        }

        private int find(int x) {//寻找根节点
            //根节点的parent[x] == x
            //这段代码的逻辑:x=parent[x],x赋值为其父节点的值
            //也就是向根节点逼近
            while (x != parent[x]) {
                parent[x] = parent[parent[x]];
                x = parent[x];
            }
            return x;
        }
    }
}
